#include<cstdlib>
#include<vector>
#include<cstring>
#include<map>
#include<set>
#include"PrintTem.h"
#include "cgc.h"
using namespace std;

typedef union { double u; void *s; long l; } L_Umaxalign;

//对齐8字节
union GCMemory{ 
    L_Umaxalign dummy; 
    struct {
        unsigned char marked;
        size_t len;
    } v;
    //后面实际内存
};

struct GCState{
    std::vector<GCMemory*> allMem;
    std::vector<GCMemory*> root;
    std::vector<GCMemory*> markedList;
};

GCState *InitGC(){
    return (new GCState());
}
void *AllocRoot(GCState *gc, size_t len){
    auto tl = sizeof(GCMemory)+len;
    auto nm = (GCMemory*)malloc(tl);
    std::memset(nm, 0, tl);
    nm->v.len = len;
    nm->v.marked = 0;
    gc->allMem.push_back(nm);
    gc->root.push_back(nm);
    return nm+1;
}

void *AllocOther(GCState *gc, size_t len){
    auto tl = sizeof(GCMemory)+len;
    auto nm = (GCMemory*)malloc(tl); 
    std::memset(nm, 0, tl);
    nm->v.len = len;
    nm->v.marked = 0;
    gc->allMem.push_back(nm);
    return nm+1;
}

//GC只管理堆上对象
//堆上对象不受stack对象控制
//遍历所有mark对象
void Mark(GCState *gc){
    gc->markedList.clear();
    for(auto it = gc->root.begin(); it != gc->root.end(); it++){
        if(!(*it)->v.marked) {
            (*it)->v.marked = 1;
            gc->markedList.push_back(*it);
        }
    }
    //寻找内存里面的指针指向我分配的GC对象的下一个位置
    //扫描内存法内存需要对齐
    std::map<void*, GCMemory*> addressToMem;
    for(auto it = gc->allMem.begin(); it != gc->allMem.end(); it++){
        addressToMem[(*it)+1] = *it;
    }
    for(auto i = 0; i < gc->markedList.size(); i++){
        auto oneMark = gc->markedList[i];
        auto alloc = (void*)(oneMark+1);
        auto len = oneMark->v.len;
        auto start = (void**)(oneMark+1);
        //检查对象内部有没有引用Pointer
        for(auto j = 0; j < len/sizeof(void*); j++){
            auto curP = start+j;
            if(addressToMem.find(*curP) != addressToMem.end()){
                auto mem = addressToMem[*curP];
                if(!mem->v.marked) {
                    mem->v.marked = 1;
                    gc->markedList.push_back(mem);
                }
            }
        }
    }
    DumpGarbage(gc);
    gc->markedList.clear();
}

void Sweep(GCState *gc){
    for(auto i = 0; i < gc->allMem.size(); ){
        auto mem = gc->allMem[i];
        if(!mem->v.marked) {
            gc->allMem.erase(gc->allMem.begin()+i);
            free(mem);
        }else {
            mem->v.marked = 0;
            i++;
        }
    }
}

void GarbageCollect(GCState *gc){
    Mark(gc);
    DumpGarbage(gc);
    Sweep(gc);
    DumpGarbage(gc);
}

void DumpGarbage(GCState *gc){
    print("GCState", "all", gc->allMem.size(), "mark", gc->markedList.size(), "root", gc->root.size());
}
